"""
3258. 统计满足 K 约束的子字符串数量 I
简单
相关标签
相关企业
提示
给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数，表示 s 的所有满足 k 约束 的
子字符串
的数量。



示例 1：

输入：s = "10101", k = 1

输出：12

解释：

s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "1010101", k = 2

输出：25

解释：

s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = "11111", k = 1

输出：15

解释：

s 的所有子字符串都满足 k 约束。



提示：

1 <= s.length <= 50
1 <= k <= s.length
s[i] 是 '0' 或 '1'。
"""
class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        start = result = num0 = num1 = 0
        # for 循环本身就自带一个向右的指针
        for end,ch in enumerate(s):
            if ch=='1':
                num1+=1
            else:
                num0+=1

            # 如果窗口内的 '0' 和 '1' 数量都超过 k，移动左指针缩小窗口，只要有一方没超过k，就可以满足k约束可以继续往后看
            while num1 > k and num0 > k:
                if s[start]=='1':
                    num1 -= 1
                else:
                    num0 -= 1
                    # 如果跳出循环,即0或1的数量超过k了,前移start
                start += 1
            #     跳出循环后num1<=k and num0<=
            result += end - start+1
        return result
if __name__ == '__main__':
    print(Solution().countKConstraintSubstrings(s = "10101", k = 1))
